#pragma once

// Classy
template<class> class CLinkedList;
template<class> class CList;

template<class T>
class CLList
{
	T		*	m_pNext;
	T		*	m_pPrev;
	
public:
	inline void		Next(T *p)				{m_pNext = p;}
	inline void		Prev(T *p)				{m_pPrev = p;}
	
	void		InsertNext(const T *p)
	{
		p->Next(Next());
		p->Prev(this);
		Next()->Prev(p);
		Next(p);
	}
	void		InsertPrev(const T *p)
	{
		p->Next(this);
		p->Prev(Prev());
		Prev()->Next(p);
		Prev(p);
	}
	
	inline T		*	Next() const		{return m_pNext;}
	inline T		*	Prev() const		{return m_pPrev;}
};

template<class T> class CLListEx;
template<class T> class CLinkPtr;

template<class T>
class CLink
{
	friend CLListEx<T>;
	friend CLinkPtr<T>;
	typedef CLink<T> 	LLink;
	typedef LLink	*	LLinkPtr;
	typedef LLink	&	RLink;

	LLinkPtr		m_pNext;
	LLinkPtr		m_pPrev;
	T				m_pThis;

	void			Set(T p)				{m_pThis = p;}
	void			Next(const LLinkPtr p)	{m_pNext = p;}
	void			Prev(const LLinkPtr p)	{m_pPrev = p;}

	CLink()				:	m_pNext(nullptr),
							m_pPrev(nullptr)
	{
	}
	CLink(T const & p, LLinkPtr q=nullptr, LLinkPtr bad=nullptr)
		:	m_pThis(p),
			m_pNext(q ? q->Next() : bad),
			m_pPrev(q ? q : bad)
	{
		if(m_pPrev != bad)
		{
			if(m_pPrev->Next() != bad) q->Next()->Prev(this);
			m_pPrev->Next(this);
		}
	}

public:
	~CLink()
	{
		if(m_pNext != this) delete m_pNext;
	}
	
	inline T const		&	Get() const				{return m_pThis;}
	inline const LLinkPtr	Next() const			{return m_pNext;}
	inline const LLinkPtr	Prev() const			{return m_pPrev;}
};

template<class T>
class CLinkPtr
{
	friend CLListEx<T>;
	typedef CLink<T>		LLink;
	typedef LLink		*	LLinkPtr;
	typedef LLink		&	RLink;
	typedef CLinkPtr<T>		ILink;
	typedef CLinkPtr<T>	&	IRLink;

	LLinkPtr				m_pLink;

public:
	CLinkPtr() : m_pLink(nullptr)
	{
	}
	CLinkPtr(RLink Link) : m_pLink(&Link)
	{
	}
	~CLinkPtr()
	{
	}
	
	inline IRLink		operator=(const IRLink o)
	{
		m_pLink = o.m_pLink;
		return *this;
	}
	inline IRLink		operator=(const RLink o)
	{
		m_pLink = &o;
		return *this;
	}
	inline IRLink		operator++()
	{
		m_pLink = m_pLink->Next();
		return *this;
	}
	inline IRLink		operator--()
	{
		m_pLink = m_pLink->Prev();
		return *this;
	}
	inline ILink		operator++(int)
	{
		ILink it = *this;
		m_pLink = m_pLink->Next();
		return it;
	}
	inline ILink		operator--(int)
	{
		ILink it = *this;
		m_pLink = m_pLink->Prev();
		return it;
	}
	inline T const	&	operator*() const					{return m_pLink->Get();}
	inline T const	&	operator->() const					{return m_pLink->Get();}
	inline bool		operator==(const RLink a) const			{return m_pLink == &a;}
	inline bool		operator!=(const RLink a) const			{return !(*this == a);}
	inline bool		operator==(const IRLink a) const		{return m_pLink == a.m_pLink;}
	inline bool		operator!=(const IRLink a) const		{return !(*this == a);}
};

template<class T>
class CLListEx
{
public:
	typedef CLink<T>		LLink;
	typedef LLink		*	LLinkPtr;
	typedef LLink		&	RLink;
	typedef CLinkPtr<T>		ILink;
	typedef CLinkPtr<T>	&	IRLink;

private:
	LLinkPtr		m_pFirst;
	LLinkPtr		m_pLast;
	LLinkPtr		m_pEnd;
	
public:
	CLListEx()
	{
		Init();
	}
	~CLListEx()
	{
		Clear();
	}

	void	Init()
	{
		if(!m_pFirst || m_pFirst == m_pEnd)
		{
			m_pFirst = nullptr;
			m_pLast = nullptr;
			m_pEnd = new LLink();
			m_pEnd->Next(m_pEnd);
			m_pEnd->Prev(m_pEnd);
		}
	}

	void	Clear()
	{
		if(m_pFirst)
			delete m_pFirst;
		m_pFirst = nullptr;
		m_pLast = nullptr;
	}
	void	Add(T const& p)
	{
		auto pLast = m_pLast;
		m_pLast = new LLink(p, pLast, m_pEnd);
		if(!m_pFirst) m_pFirst = m_pLast;
	}
	void	Drop(ILink const& it)
	{
		if(it == Begin())
			m_pFirst = it.m_pLink->Next();
		if(it == End())
			m_pLast = it.m_pLink->Prev();
		it.m_pLink->Next()->Prev(it.m_pLink->Prev());
		it.m_pLink->Prev()->Next(it.m_pLink->Next());
		m_pEnd->Next(m_pEnd);
		m_pEnd->Prev(m_pEnd);
	}

	inline ILink	Begin() const
	{
		return m_pFirst ? *m_pFirst : *m_pEnd;
	}
	inline ILink	End() const
	{
		return m_pLast ? *m_pLast : *m_pEnd;
	}
	inline ILink	Bad() const
	{
		return *m_pEnd;
	}
};

// Binary tree nodes
template<class T>
class CNode
{
	friend			CList<T>;
	int				m_nKey;
	T			*	m_pObject;
	CNode<T>	*	m_pLeft;
	CNode<T>	*	m_pRight;
	CNode<T>	*	m_pRoot;

	CNode(int key, T * object)
	{
		m_nKey = key;
		m_pObject = object;
		m_pLeft = nullptr;
		m_pRight = nullptr;
		m_pRoot = nullptr;
	}
	~CNode()
	{
		if(m_pLeft) delete m_pLeft;
		if(m_pRight) delete m_pRight;
	}
	inline void SetLeft(CNode<T> * pNode)
	{
		if(m_pLeft)
		{
			if(pNode->m_nKey < m_pLeft->m_nKey)
				m_pLeft->SetLeft(pNode);
			else
				m_pLeft->SetRight(pNode);
		}
		else
		{
			m_pLeft = pNode;
			pNode->m_pRoot = this;
		}
	}
	inline void SetRight(CNode<T> * pNode)
	{
		if(m_pRight)
		{
			if(pNode->m_nKey < m_pRight->m_nKey)
				m_pRight->SetLeft(pNode);
			else
				m_pRight->SetRight(pNode);
		}
		else
		{
			m_pRight = pNode;
			pNode->m_pRoot = this;
		}
	}
	void Drop()
	{
		if(!m_pLeft && !m_pRight)
		{
			if(m_pRoot->m_pLeft == this)
				m_pRoot->m_pLeft = nullptr;
			else
				m_pRoot->m_pRight = nullptr;
		}
		else
		{
			if(m_pRoot->m_pLeft == this)
			{
				if(m_pRight) m_pRoot->SetLeft(m_pRight);
				if(m_pLeft) m_pRoot->SetLeft(m_pLeft);
			}
			else
			{
				if(m_pRight) m_pRoot->SetRight(m_pRight);
				if(m_pLeft) m_pRoot->SetRight(m_pLeft);
			}
		}
		m_pLeft = nullptr;
		m_pRight = nullptr;
		delete this;
	}
};

// Binary tree list
template<class T>
class CList
{
	CNode<T> *		m_pBase;
	CNode<T> *		m_pCurrentNode;

	// Add to sub-left of the current node if it's lower, right if it's higher
	void Add(int key, T * object, CNode<T>* node)
	{
		if(key < node->m_nKey)
		{
			if(node->m_pLeft) Add(key, object, node->m_pLeft);
			else
			{
				node->m_pLeft = new CNode<T>(key, object);
				node->m_pLeft->m_pRoot = node;
			}
		}
		else
		{
			if(node->m_pRight) Add(key, object, node->m_pRight);
			else
			{
				node->m_pRight = new CNode<T>(key, object);
				node->m_pRight->m_pRoot = node;
			}
		}
	}

	// Search a branch for the key
	CNode<T> * Search(int key, CNode<T>* node) const
	{
		if(node)
		{
			if(key == node->m_nKey) return node;
			return key < node->m_nKey ? Search(key, node->m_pLeft) : Search(key, node->m_pRight);
		}
		return nullptr;
	}
	CNode<T> * SearchForHighest(CNode<T>* node)
	{
		if(node) return node->m_pRight ? SearchForHighest(node->m_pRight) : node;
		return nullptr;
	}
	CNode<T> * SearchForLowest(CNode<T>* node)
	{
		if(node) return node->m_pLeft ? SearchForLowest(node->m_pLeft) : node;
		return nullptr;
	}
	CNode<T> * SearchForHighest(int max, CNode<T>* node)
	{
		if(node)
		{
			if(node->m_nKey < max)
			{
				if(node->m_pRight) return node->m_pRight->m_nKey < max ? SearchForHighest(max, node->m_pRight) : node;
				return node;
			}
			return node->m_pLeft ? SearchForHighest(max, node->m_pLeft) : nullptr;
		}
		return nullptr;
	}
	CNode<T> * SearchForLowest(int min, CNode<T>* node)
	{
		if(node)
		{
			if(node->m_nKey >= min)
			{
				if(node->m_pLeft) return node->m_pLeft->m_nKey >= min ? SearchForLowest(min, node->m_pLeft) : node;
				return node;
			}
			return node->m_pRight ? SearchForLowest(min, node->m_pRight) : nullptr;
		}
		return nullptr;
	}

public:
	CList()
	{
		m_pBase = nullptr;
		m_pCurrentNode = nullptr;
	}
	~CList()
	{
		delete m_pBase;
	}

	void Clear()
	{
		delete m_pBase;
		m_pBase = nullptr;
	}
	void ClearNoDelete()
	{
		m_pBase = nullptr;
	}
	void Add(int key, T * object)
	{
		if(m_pBase) Add(key, object, m_pBase);
		else m_pBase = new CNode<T>(key, object);
	}
	void Drop(int key, T * object)
	{
		auto pNode = Search(key, m_pBase);
		while(pNode && pNode->m_pObject != object)
			pNode = pNode->m_pRight->m_nKey == key ? pNode->m_pRight : nullptr;
		if(pNode) pNode->Drop();
	}

	T * Get(int key)
	{
		m_pCurrentNode = Search(key, m_pBase);
		return m_pCurrentNode ? m_pCurrentNode->m_pObject : nullptr;
	}
	T * Get(int key) const
	{
		auto pCurrentNode = Search(key, m_pBase);
		return pCurrentNode ? pCurrentNode->m_pObject : nullptr;
	}
	T * GetHighest(int max=0)
	{
		m_pCurrentNode = max ? SearchForHighest(max, m_pBase) : SearchForHighest(m_pBase);
		return m_pCurrentNode ? m_pCurrentNode->m_pObject : nullptr;
	}
	T * GetLowest(int min=0)
	{
		m_pCurrentNode = min ? SearchForHighest(max, m_pBase) : SearchForHighest(m_pBase);
		return m_pCurrentNode ? m_pCurrentNode->m_pObject : nullptr;
	}
	T * Next()
	{
		if(!m_pCurrentNode || !m_pCurrentNode->m_pRight) return nullptr;
		if(m_pCurrentNode->m_pRight->m_nKey != m_pCurrentNode->m_nKey) return nullptr;
		m_pCurrentNode = m_pCurrentNode->m_pRight;
		return m_pCurrentNode->m_pObject;
	}
};

template<class> class CCatalogue;

template<class T>
class CCatalogueEntry
{
	friend CCatalogue<T>;
	int					m_nIndex;
	DWORD				m_nKey;
	T *					m_pObject;
	CCatalogueEntry *	m_pLeft;
	CCatalogueEntry *	m_pRight;

	CCatalogueEntry(int key, T* object)
	{
		m_nIndex = 0;
		m_nKey = key;
		m_pObject = object;
		m_pLeft = nullptr;
		m_pRight = nullptr;
	}
	~CCatalogueEntry()
	{
		delete m_pRight;
	}
};

template<class T>
class CCatalogue
{
	CCatalogueEntry<T>	*	m_pBegin;
	CCatalogueEntry<T>	*	m_pMiddle;
	CCatalogueEntry<T>	*	m_pEnd;
	int						m_nNumEntries;
	int						m_nFirstKey;
	int						m_nLastKey;

	void Add(DWORD key, T * object, CCatalogueEntry<T>* entry)
	{
		if(key < entry->m_nKey)
		{
			if(entry->m_pLeft)
			{
				if(entry->m_pLeft->m_nKey < key) return Insert(key, object, entry->m_pLeft);
				else return Add(key, object, entry->m_pLeft);
			}
			else
			{
				entry->m_pLeft = new CCatalogueEntry<T>(key, object);
				entry->m_pLeft->m_pRight = entry;
				m_pBegin = entry->m_pLeft;
				entry->m_nIndex = m_nNumEntries++;
			}
		}
		else
		{
			if(entry->m_pRight)
			{
				if(entry->m_pRight->m_nKey > key) return Insert(key, object, entry);
				else return Add(key, object, entry->m_pRight);
			}
			else
			{
				entry->m_pRight = new CCatalogueEntry<T>(key, object);
				entry->m_pRight->m_pLeft = entry;
				m_pEnd = entry->m_pRight;
				entry->m_nIndex = m_nNumEntries++;
			}
		}
	}
	void Insert(DWORD key, T * object, CCatalogueEntry<T>* entry)
	{
		CCatalogueEntry<T> * newentry = new CCatalogueEntry<T>(key, object);
		newentry->m_pLeft = entry;
		newentry->m_pRight = entry->m_pRight;
		if(entry->m_pRight) entry->m_pRight->m_pLeft = newentry;
		entry->m_pRight = newentry;
		newentry->m_nIndex = m_nNumEntries++;
	}

	T * Lookup(DWORD key, CCatalogueEntry<T>* entry)
	{
		if(entry)
		{
			if(key == entry->m_nKey) return entry->m_pObject;
			return entry->m_pRight && entry->m_pRight->m_nKey <= key ? Lookup(key, entry->m_pRight) : nullptr;
		}
		return nullptr;
	}
	T * Lookdown(DWORD key, CCatalogueEntry<T>* entry)
	{
		if(entry)
		{
			if(key == entry->m_nKey) return entry->m_pObject;
			return entry->m_pLeft && entry->m_pLeft->m_nKey >= key ? Lookdown(key, entry->m_pLeft) : nullptr;
		}
		return nullptr;
	}

	// "look all around..." - RIP Pippin.

public:
	CCatalogue()
	{
		m_pBegin = nullptr;
		m_pMiddle = nullptr;
		m_pEnd = nullptr;
		m_nFirstKey = 0;
		m_nLastKey = 0;
		m_nNumEntries = 0;
	}
	~CCatalogue()
	{
		delete m_pBegin;
	}

	void Clear()
	{
		delete m_pBegin;
		m_pBegin = nullptr;
		m_pMiddle = nullptr;
		m_pEnd = nullptr;
		m_nNumEntries = 0;
	}
	void Add(DWORD key, T * object)
	{
		if(m_pBegin)
		{
			if(!m_pMiddle) m_pMiddle = m_pBegin;

			static int nMiddleBalance = -1;

			if(key > m_pMiddle->m_nKey)
			{
				if((++nMiddleBalance % 2) == 0) m_pMiddle = m_pMiddle->m_pRight;
				Add(key, object, m_pBegin);
			}
			else
			{
				if((--nMiddleBalance % 2) == 0) m_pMiddle = m_pMiddle->m_pLeft;
				Add(key, object, m_pEnd);
			}
		}
		else
		{
			m_pBegin = new CCatalogueEntry<T>(key, object);
			m_pMiddle = m_pBegin;
			m_pEnd = m_pBegin;
		}
	}
	T * Find(DWORD key)
	{
		if(m_pBegin)
		{
			if(key > m_pEnd->m_nKey - m_pBegin->m_nKey) return Lookdown(key, m_pEnd);
			else return Lookup(key, m_pBegin);
		}
		return nullptr;
	}
};